/*
 * @lc app=leetcode.cn id=188 lang=swift
 *
 * [188] 买卖股票的最佳时机 IV
 */

// @lc code=start
class Solution {
    func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
        let n = prices.count
        if n < 2 || k <= 0 { return 0 }

        var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: 2), count: k+1), count: n)
        for i in 0..<n {
            for j in stride(from: k, through: 1, by: -1) {
                if i == 0 {
                    dp[i][j][0] = 0
                    dp[i][j][1] = -prices[i]
                    continue
                }
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])
            }
        }

        return dp[n-1][k][0]
    }
}
// @lc code=end

